import java.util.HashMap;

class Solution {
    public int maxSumDivThree(int[] nums) {
        int n=nums.length;
        int sum=0;
        int x1=0x3f3f3f3f;
        int x2,y1,y2;
        x2=y1=y2=x1;
        for(int i=0;i<n;i++){
            int num=nums[i];
            sum+=num;
            if(num%3==1){
                if(num<x1){
                    x2=x1;
                    x1=num;
                }
                else if(x1<=num&&num<x2) x2=num;

            }else if(num%3==2){
                if(num<y1){
                    y2=y1;
                    y1=num;
                }
                else if(y1<=num&&num<y2) y2=num;
            }


        }
        HashMap<Integer,Integer> hash=new HashMap<>();



        if(sum%3==0) return sum;
        else if(sum%3==1){
            return Math.max(sum-x1,sum-y1-y2);
        }else return Math.max(sum-x1-x2,sum-y1);
    }
}


class Solution1 {
    public String reorganizeString(String s) {
        HashMap<Character,Integer> hash=new HashMap<>();
        char[] ss=s.toCharArray();
        int maxCount=0;
        char maxVal=0;

        for(char x:ss){
            int n=hash.getOrDefault(x,0)+1;
            hash.put(x,n);
            if(maxCount<n){
                maxCount=n;
                maxVal=x;
            }

        }

        if(maxCount>(ss.length+1)/2) return "";
        int index=0;
        for(int i=0;i<maxCount;i++){
            ss[index]=maxVal;
            index+=2;
        }

        hash.remove(maxVal);

        for(char key:hash.keySet()){
            for(int i=0;i<hash.get(key);i++){
                if(index>ss.length-1) index=1;
                ss[index]=key;
                index+=2;
            }
        }

        return String.valueOf(ss);


    }
}

class Solution2 {
    public int[] rearrangeBarcodes(int[] barcodes) {
        HashMap<Integer,Integer> hash=new HashMap<>();
        int maxCount=0;
        int maxVal=0;
        for(int x:barcodes){
            int n=hash.getOrDefault(x,0)+1;
            hash.put(x,n);
            if(maxCount<n){
                maxCount=n;
                maxVal=x;

            }
        }


        int index=0;
        for(int j=0;j<maxCount;j++){
            barcodes[index]=maxVal;
            index+=2;
        }
        hash.remove(maxVal);
        for(int key:hash.keySet()){
            for(int i=0;i<hash.get(key);i++){
                if(index>barcodes.length-1) index=1;
                barcodes[index]=key;
                index+=2;
            }
        }

        return barcodes;




    }
}


class Solution3 {
    public int tribonacci(int n) {
        if(n==0) return 0;
        if(n<3) return 1;
        int[] dp=new int[n+1];

        dp[0]=0;
        dp[1]=1;
        dp[2]=1;


        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
        }


        return dp[n];

    }
}